МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра ЕОМ / ЗВІТ ДО ЛАБОРАТОРНОЇ РОБОТИ №1 з дисципліни: «Паралельні та розподілені обчислення» на тему: «ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ ЗАСОБАМИ MPI» Варіант №26  МЕТА РОБОТИ: Вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції. Освоїти інструменти бібліотеки MPI для реалізації декомпозиції задач. 1. Завдання 1.Використовуючи метод функціональної декомпозиції, розробити алгоритм обчислення запропонованого матрично-векторного виразу, який би враховував можливість паралельного виконання і був оптимальним з точки зору часових затрат . 2. На основі створеного алгоритму написати програму використовуючи засоби МPI яка дозволяє обчислити вираз та ілюструє проведену декомпозицію для кількості процесорів заданих у варіанті. 1.1. Завдання згідно варіанту Номер варіанту Вираз який треба обчислити К-сть процесорів   Вектор y1 Вектор y2 Матриця Y3   26 
матриця 6   bi=i3+3i2-i/(2+i) ( b1c1‘A1c1’)’ A2(B2+26C2) Cij=1/(i2+j)    2. Аналіз задачі Для заданого виразу вхідними даними є: розмірність матриць – N; матриці
; вектори-стовпці
. Ці параметри повинні вводитися з клавіатури, або генеруватися випадковим чином (крім розмірності). При чому, елементи всіх матриць та векторів є цілими додатними числами, більшими за нуль. Вектор-стовпець та матриця обраховуються, виходячи з уведеної розмірності. Матриця C2 повинна генеруватись за формулою: Cij=1/(i2+j) Вектор стовпець b повинен генеруватись за формулою: bi=i3+3i2-i/(2+i) 3. Декомпозиція При утворенні y1 враховуємо, що результатом множення матриці А на вектор-стовпець b є вектор-стовпець. При утворенні y2 враховуємо, що результатом множення двох матриць є матриця. При утворенні Y3 враховуємо, результатом множення матриці на матрицю є матриці, та при її добутку на різницю матрицею буде також матриця. Таким чином, згідно поставленої задачі, в обчисленні загального виразу приймають участь два різні елементи – вектор-стовпець та матриця. Оскільки, згідно правил матричних обчислень, добуток не є комутативною операцією, всі множення слід виконувати в тій послідовності, яка задана. Правила множення наведені в таблиці 1. Таблиці 1 Результати добутків в матричних обчисленнях результатом множення матриці на матрицю є матриця. cij=
 результатом множення матриці на вектор-стовпець є вектор-стовпець. cj=
 результатом множення вектора-рядка на вектор-стовпець є число с=
 результатом множення вектора-стовпця на вектор-рядок є матриця сij=
 результатом множення двох векторів-стовпців є число. с=
 результатом множення вектора-рядка на матрицю на є вектор-рядок. сj=
  Оскільки задано якого типу повинен бути результат розв’язання задачі можна здійснити перевірку правильності декомпозиції, тобто чи за нею можна розв’язати заданий вираз згідно варіанту. Оскільки вище наведено результати Y3, y1 та y2 перевірку почнемо з 3 стадії, тобто після отримання цих результатів. Стадія 4: Результатом піднесення матриці Y3 до квадрату, тобто множення матриці саму на себе, буде матриця. Стадія 5: Результатом піднесення квадратної матриці до кубічної, тобто множення матриці Y32 на матрицю Y3 буде матриця. Результатом множення вектора- рядка y1’ на матрицю Y3 буде рядок. Результатом множення вектора-рядка y2 на вектора-стовбець y1 буде просте число. Стадія 6: Результатом множення матриці (Y33) на вектора-стовбець (y1) буде вектора-стовбець. Результатом множення вектора-рядка (y1’*Y3 ) вектора-стовбець (y1) буде просте число . Результатом множення простого числа (y2*y1) на матрицю (Y3) буде матриця . Стадія 7: Результатом множення вектора-стовбеця (Y33*y1)на вектора-рядкядок(y1’)буде матриця . Результатом множення числа(y1’*Y3* y1)на матрицю (Y3)буде матриця . Стадія 8: Результатом додавання матриці(Y33*y1* y1’)до матриці (y2*y1* Y3)буде матриця . Стадія 9: Сумою д...